#pragma once

#include "TypeDefin.h"
#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *
 * */
//翻转链表
// 1 2 3 4 5
static ListNode *reversNode(ListNode *node) {
    if (node == nullptr || node->next == nullptr)
        return node;

    //头插发 没有头结点的头插法

    //https://zhuanlan.zhihu.com/p/488188589
    ListNode *newHead = nullptr;
    ListNode *nextHead = nullptr;
    while (node != nullptr) {
        nextHead = node->next; //指向下一个node结点
        node->next = newHead;  // node 下一个指向一串翻转后的头结点
        newHead = node;        //真正头结点指针左移
        node = nextHead;       //node结点归位置
    }

    return newHead;
}


//翻转链表 结点直接翻转
// 1 2 3 4 5
static ListNode *reversNode1(ListNode *node) {
    if (node == nullptr || node->next == nullptr)
        return node;

    //头插发 没有头结点的头插法

    //https://zhuanlan.zhihu.com/p/488188589
    ListNode *nextNextNode = node;//
    ListNode *end = node->next;
    // 1 2 3 4 4
    while (end != nullptr) {
        //1-3
        nextNextNode = end->next;//保留下一个指针

        end->next = node;//2-1
        node = end;// node永远指向第一个节点
        end = nextNextNode; //3
    }


    return node;
}

//递归翻转 返回翻转后的头结点
static ListNode *reversNode2(ListNode *node) {
    if (node == nullptr || node->next == nullptr)
        return node;


    // 1 2 3 4
    ListNode *p = reversNode2(node->next);//递归到最后一个 这个必须写在前面。。感觉有点不一样

    //其实这边算是单个的头 一个一个翻转的 这里p返回的感觉不像一个整体
    node->next->next = node;//翻转 挺精华的
    node->next = nullptr;//


    return p;

}

//已经弃用
static ListNode *reversNode3(ListNode *node) {
    if (node == nullptr || node->next == nullptr)
        return node;


    // 1 2 3 4

    ListNode *nextNext = node->next;
    //其实这边算是单个的头 一个一个翻转的 这里p返回的感觉不像一个整体
    node->next->next = node;//翻转 挺精华的
    node->next = nullptr;//

    ListNode *p = reversNode3(nextNext);//递归到最后一个 这个必须写在前面。。感觉有点不一样


    return p;

}


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
